import copy
nn=3

solution=[]

def MinMax(gamestate,n,l,depth):
    global solution 
    childlist=[]
    beststate=[]
    if(draw(gamestate,n)):
        cost = 1
        #print 'draw'
        #print solution
        return [1,cost,gamestate]    
    elif(win(gamestate,n) == True):
        #print gamestate        
        if l == 1: 
            cost = 2
            #print 'losennnnnnnnnnnnnn', gamestate,cost
            #print solution
            return [0, cost,gamestate]
        else:             
            cost = 0
            #print 'winnnnnnnnnnnnnnn'
            #print solution
            return [2, cost,gamestate]     
        
    ret = 0    
    #print gamestate 
    if depth==0:
        bestcost = 0
        beststate = gamestate
    else:
        for i in range(0,n*n):
            state = copy.deepcopy(gamestate)
            if state[i] == 0:                    
                state[i] = l
                childlist.append(state)
                
        #solution.append(childstate) 
        depthC = copy.deepcopy(depth)          
        if l==1:    #player MIN         
            bestcost = 10
            for childstate in childlist:
                #print childstate
                solution.append(childstate)         
                costN = MinMax(childstate, n, -1, depth-1)[1]
                #if(depth==2):
                    #print costN,childstate,depth
                #if depth==5:
                    #print costN,childstate,bestcost,beststate                
                if costN < bestcost:
                    bestcost = costN                
                    beststate = childstate
                solution.pop()
                #if depth==7:
                    #print costN,childstate,bestcost,beststate,depth
            #print 'level',depthC,beststate,bestcost     
        else:   #2ND player MAX
            bestcost = -10
            for childstate in childlist:
                solution.append(childstate)
                costN = MinMax(childstate, n, 1, depth-1)[1]
            #if(depth==5):
                #print costN,childstate,depth 
                #if depth==5:
                    #print costN,childstate          
                if costN > bestcost:                
                    bestcost = costN
                    beststate = childstate
                solution.pop()
                #if depth==7:
                    #print costN,childstate,bestcost,beststate,depth 
        #print 'level',depthC,beststate,bestcost
        #if(depth==3):
            #print childlist,depth
            #solution.pop()
      
    return [-1, bestcost,beststate]  
    
def test(n):
    openlist=[]    
    if(n==0):
        return    
    openlist.append(n)
    print openlist
    test(n-1)    
    print openlist;
    
def draw(state,n):
    for i in range(0,n*n):
        if state[i]==0:
            return False
    
    return True
    
def win(state,n):
    for i in range(0,n):
        ret = 0
        for j in range(0,n): #row
            ret = ret + state[i*n+j]
            if(ret == n or ret == n*(-1)):
                return True
                
        ret = 0
        for j in range(0,n):#colunm
            ret = ret + state[i+n*j]
            if(ret == n or ret == n*(-1)):
                return True
    
    return False

def ticgame(n):
    gamesolution=[]
    gamestateinput=[]
    for i in range(0,n*n):
        gamestateinput.append(0)
    
    #gamestateinput = [1, -1, 0, 0, -1, -1, 0, 1, 1]
    gamestate=[-1, 1, gamestateinput]
    gamesolution.append(gamestateinput) 
    #MinMax(gamestate[2], , 1, 16)
    while True:       
        # 1 means player
        # 9 means max step        
        gamestate = MinMax(gamestate[2], n, 1, 7)
        print 'player 1 turn', gamestate[2]
        gamesolution.append(gamestate[2]) 
        if(gamestate[0]==0):
            print 'player 2 win'
            break            
        elif win(gamestate[2],n):
            print 'player 1 win'
            break            
        elif  draw(gamestate[2],n):
            print 'draw'
            break
                       
        row = input("Enter the row: ")
        col = input("Enter the column: ")
        while(gamestate[2][row*n+col]!=0):
            print 'error,again'
            row = input("Enter the row: ")
            col = input("Enter the column: ")
        
        #player 2 turn
        gamestate[2][row*n+col] = -1
        print 'player 2 turn', gamestate[2]
        gamesolution.append(gamestate[2])
                        
    print gamesolution
                   
        #print gamestate
        
        
            
#test(5)

#statetemp = [0, -1, 0, 0, -1, 1, 1, -1, 1]
#print win(statetemp,3)
ticgame(nn)
#print solution